package org.example.everyday;

import java.util.ArrayList;
import java.util.List;

public class FindMinFibonacciNumbers {

    public static void main(String[] args) {
        FindMinFibonacciNumbers f  = new FindMinFibonacciNumbers();
        int result = f.findMinFibonacciNumbers(6);
        System.out.println(result);
    }


    public int findMinFibonacciNumbers(int k) {
       List<Integer> f = new ArrayList<>();
       int a = 1,b = 1;
       f.add(1);
       while(a+b<=k){
           int sum = a + b;
           f.add(sum);
           a = b;
           b = sum;
       }
       int ans = 0;
        for (int i = f.size()-1; i>=0 && k>0 ; i--) {
            int value = f.get(i);
            if(k>=value){
                k-=value;
                ans++;
            }
        }
        return ans;
    }
}
